{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.1-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 二叉数与递归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 概念"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**完全二叉树**的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。\n",
    "```\n",
    "    1\n",
    "   / \\\n",
    "  2   3\n",
    " / \\  /\n",
    "4  5 6\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**满二叉树** ：所有层的节点数达到最大"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在一颗数中查找一个键"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def contain(root, key):\n",
    "    if root is None:\n",
    "        return False\n",
    "    \n",
    "    if root.val == key:\n",
    "        return True\n",
    "    \n",
    "    return contain(root.left, key) or contain(root.right, key)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# test\n",
    "from leetcode_test import TreeNode\n",
    "\n",
    "t = TreeNode.create([1,2,3,4,5])\n",
    "contain(t, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "释放一个二叉树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def destroy(root: TreeNode):\n",
    "    if root is None:\n",
    "        return \n",
    "    destroy(root.left)\n",
    "    destroy(root.right)\n",
    "    del root\n",
    "\"\"\"\n",
    "del 是删除引用而不是删除对象，对象由自动垃圾回收机制（GC）删除，当某个对象的所有引用都被删除后，会自动执行魔法方法__del__来清除此垃圾。所以这个例子并没有用\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "2"
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# test\n",
    "t = TreeNode.create([1,2,3,4,5])\n",
    "destroy(t)\n",
    "t.left.val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "反转二叉树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def invertTree(root: TreeNode):\n",
    "    if not root:\n",
    "        return \n",
    "    invertTree(root.left)\n",
    "    invertTree(root.right)\n",
    "    root.left, root.right = root.right, root.left\n",
    "    return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "[<leetcode_test.leetcode_test.TreeNode object at 0x7f291ed2d850>, <leetcode_test.leetcode_test.TreeNode object at 0x7f291ed2d400>]\n[<leetcode_test.leetcode_test.TreeNode object at 0x7f291ed2ddc0>, <leetcode_test.leetcode_test.TreeNode object at 0x7f291ed2d820>, <leetcode_test.leetcode_test.TreeNode object at 0x7f291ed2d6a0>, <leetcode_test.leetcode_test.TreeNode object at 0x7f291ed2dc10>]\n[None, None, None, None, None, None, None, None]\n"
    },
    {
     "data": {
      "text/plain": "[4, 7, 2, 9, 6, 3, 1]"
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t = TreeNode.create([4,2,7,1,3,6,9])\n",
    "n = invertTree(t)\n",
    "n.get_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 提醒\n",
    "\n",
    "### 当碰到有叶子节点的题目的时候\n",
    "\n",
    "```python\n",
    "if not root.left and not root.right:\n",
    "    pass\n",
    "```\n",
    "\n",
    "表示你需要这个判断条件"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}